var arithmetic = {};
/**
 * 1.判断一个单词是否是回文数
 *  world:string
 * return: boolean
 */
arithmetic.checkPalindrom = function(word) {
  return word == word.split('').reverse().join('');
}
/**
 * 2.去掉一组整型数组重复的值
 * arr: Array
 * return : Array
 */
arithmetic.unique = function(arr) {
  var tempObj = {},
    newArr = [];
  for (var i = 0, len = arr.length; i < len; i++) {
    var cur = arr[i];
    if (!tempObj[cur]) {
      tempObj[cur] = 1;
      newArr.push(cur);
    } else {
      tempObj[cur]++;
    }
  }
  return newArr;
}
/**
 * 3. 统计一个字符串出现最多的字母
 */
arithmetic.findMaxDuplicateChar = function(str) {
  var map = {},
    maxLen = 0,
    moreStr = '';
  for (var i = 0, len = str.length; i < len; i++) {
    if (!map[str[i]]) {
      map[str[i]] = 1;
    } else {
      map[str[i]]++;
    }
  }
  for (var k in map) {
    if (map[k] > maxLen) {
      map[k] = maxLen;
      moreStr = k;
    }
  }
  return moreStr;
}
/**
 * 4. 冒泡排序算法
 */
arithmetic.bubbleSort = function(arr) {

}
/**
 * 5. 快速排序算法
 */
//算法步骤：
//(1)先从数列中取出一个数作为"基准"
//(2)分区过程：将比这个"基准"大的数全放到"基准"的右边，小于或等于"基准"的数全放到"基准"的左边
//(3)再对左右区间重复第二步
arithmetic.quickSort = function(arr) {
  if (arr.length === 1) {
    return arr;
  }
  var baseIndex = Math.floor(arr.length / 2); //基准位置(可以任意的选取)
  // splice返回的是删除的数组, 参数1是开始的索引, 参数2：删除的个数
  var base = arr.splice(baseIndex, 1)[0]; // 基准数
  var left = [],
    right = [];
  for (var i = 0, len = arr.length; i < len; i++) {
    if (base > arr[i]) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return arithmetic.quickSort(left).concat([base], arithmetic.quickSort(right)); // 链接左数组， 基准数构成的数组，右数组
}
/**
 * 5.2 选择排序
 */
// 算法描述
// 1. 在未排序序列中找到最小(大)的元素，存放到排列序列的起始位置
// 2. 从剩余未排序元素中继续寻找最小(大)的元素，然后放到已排序序列的末尾
// 3. 重复第二步，直到所有元素均排序完成
arithmetic.selectSort = function(arr) {
  var len = arr.length;
  var temp, minIndex;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if(arr[j] < arr[minIndex]) {//寻找最小的数
        minIndex = j;// 找到最小数的位置
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
};

/**
 * 6. 插入排序算法
 */
arithmetic.insertSort = function(arr) {

};
/**
 * 7. 希尔排序算法
 */
arithmetic.hashSort = function(arr) {


}
/**
 * 8. 不借助临时变量，进行两个整数的交换
 */
arithmetic.exchangeNumber = function(num1, num2) {
  num1 = num1 + num2;
  num2 = num1 - num2;
  num1 = num1 - num2;
  return num1 + ' ' + num2
}
/**
 * 9. 斐波纳契数列的实现
 * 例如： 0 1 1 2 3 5 8...
 * num: 数列的长度 Number
 */
// 得到对应的那个数列长度的值
arithmetic.fibo = function(num) {
  if (num === 0 || num === 1) {
    return num;
  }
  return arithmetic.fibo(num - 1) + arithmetic.fibo(num - 2);
}
// fib序列
arithmetic.getFibo = function(num) {
  var arr = [],
    i = 0;
  while (i < num) {
    if (i <= 1) {
      arr.push(i)
    } else {
      arr.push(arr[i - 1] + arr[i - 2])
    }
    i++;
  }
  return arr;
}
/**
 * 10. 找出下列正数组的最大差值比如:
 * 思路：每次使用差值与定义的最大差值进行比较，然后在重新赋值
 */
arithmetic.getMaxProfit = function(arr) {
  var maxProfit = 0,
    minValue = arr[0];
  for (var i = 1, len = arr.length; i < len; i++) {
    var curValue = arr[i];
    minValue = Math.min(curValue, minValue);
    var tempProfit = curValue - minValue;
    maxProfit = Math.max(tempProfit, maxProfit)
  }
  return maxProfit;
}
/**
 * 11. 随机生成指定长度的字符串
 */
arithmetic.randomString = function(num) {
  // toString(radix) 方法可把一个Number对象转换为一个字符串，并返回其结果
  // radix: 可选。规定表示数字的基数，使 2 ~ 36 之间的整数。若省略该参数，则使用基数 10。但是要注意，如果该参数是 10 以外的其他值，则 ECMAScript 标准允许实现返回任意值。
  // console.log(Math.random().toString(32))
  // console.log(Math.random().toString(32).replace(/[^a-z]+/g, ''))
  return Math.random().toString(32).replace(/[^a-z]+/g, '').substr(0, num);
}
/**
 * 12. 二叉查找树
 */
// 二叉查找树的特点：
// ① 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
// ② 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
// ③ 任意节点的左、右子树也分别为二叉查找树；
// ④ 没有键值相等的节点。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

/**
 * 12. 求n的阶乘
 * @param n
 */
arithmetic.factorial = function(n) {
  // console.trace();//查看每一次当前的调用栈的状态
  if (n === 0) {
    return 1;
  }
  return n * arithmetic.factorial(n - 1);
}
//改进方法
//使用尾递归
// 是一种递归的写法，可以避免不断的将函数压栈最终导致堆栈溢出。通过设置一个累加参数，并且每一次都将当前的值累加上去，然后递归调用。
arithmetic.factorial1 = function(n, total = 1) {
  console.trace();
  if (n === 0) {
    return total
  }
  return arithmetic.factorial1(n - 1, n * total)
}
//注意：尾递归不一定会将你的代码执行速度提高；相反，可能会变慢。不过，尾递归可以让你使用更少的内存，使你的递归函数更加安全 (前提是你要开启harmony模式)。
